/**
 *  递归是从下到上开始计算，他是一直蒙着头往下走，当走到叶子节点的时候在回去。实 际上我们还可以从上到下来计算，也就是这里讲的动态规划。
 *  定义dp[i]表示前i个字符的解码数。
 * 如果要求前i个字符的解码数 
 *      我们可以先求前i -1个字符的解码数，但前提条件是当前字符也可以解码（一个字符的 话，只要不是0，都可以） 
 *      还可以求前i -2个字符的解码数，但前提条件是当前字符和前一个字符构成的两个数字 是有效的，也就是小于等于26。
 *  每次截取一个或者每次截取两个，看到这里大家应该已经明白了，如果没有条件限制的 话，这题解法和356，青蛙跳台阶相关问题完全一样，
 *  每次跳一个台阶或者每次跳两个 台阶，递归公式其实就是个斐波那契数列
 * 
 *      dp[i]=dp[i -1]+dp[i -2]
 * 
 *  只不过这里的斐波那契数列是有条件限制的，需要根据条件判断哪一项该加，哪一项不 该加，但原理都差不多，来看下代码
 * */


// 优化前
function numDecodings(s) {
    var len = s.length;
    var dp = new Array(len + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= len; i++) {
        //判断截取一个是否符合（只要不是0，都符合）
        if (s.charAt(i - 1) != '0') {
            dp[i] += dp[i - 1];
        }
        //判断截取两个是否符合
        if (
            i >= 2 &&
            (s.charAt(i - 2) == '1' || s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')
        ) {
            dp[i] += dp[i - 2];
        }
    }
    console.log(dp);
    return dp[len];
}

// 优化后
function numDecodings(s) {
    var len = s.length;
    var lastLast = 0;
    var last = 1;

    for (let i = 0; i < len; i++) {
        var cur = 0;
        if (s.charAt(i) != '0') {
            cur = last;
        }
        if (i >= 1 && (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2' && s.charAt(i) <= '6')) {
            cur += lastLast;
        }
        lastLast = last;
        last = cur;
    }

    return last;
}